package leetcode.editor.cn.dsa18_searchtree;

import java.util.ArrayList;
import java.util.List;

public class BinarySearchTree {
    public static void main(String[] args) {
        BinarySearchTree searchTree = new BinarySearchTree();
        TreeNode treeNode = null;
        treeNode = searchTree.addNode(treeNode, 5);
        treeNode = searchTree.addNode(treeNode, 2);
        treeNode = searchTree.addNode(treeNode, 8);
        treeNode = searchTree.addNode(treeNode, 5);
        treeNode = searchTree.addNode(treeNode, 9);
        System.out.println(searchTree.inorderTraversal(treeNode));
        // 打印中序遍历序列：[2, 5, 5, 8, 9]
        System.out.println(searchTree.searchBST(treeNode, 9));
        System.out.println(searchTree.searchBST(treeNode, 10));
    }
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 向二叉搜索树插入节点
     */
    public TreeNode addNode(TreeNode node, int item) {
        // 空二叉树，创建一个节点，然后作为根节点返回
        if (node == null) {
            return new TreeNode(item);
        }
        // 递归调用获取插入元素后的根节点
        // 然后将返回的根节点与当前节点进行连接
        if (item < node.val) {
            node.left = addNode(node.left, item);
        } else {
            node.right = addNode(node.right, item);
        }
        return node; //返回连接后的根节点
    }

    /**
     * 在二叉搜索树中查询是否存在给定值
     * 递归方式
     */
    public boolean searchBST(TreeNode root, int value) {
        // 递归终止条件 + 边界问题
        if(root == null) return false;
        // 如果查找值与当前结点相等，返回真
        if(value == root.val) return true;
        // 如果查找值小于根结点值，在左子树中查找
        if(value < root.val) return searchBST(root.left,value);
        // 如果查找值大于等于根结点值，在右子树中查找
        else return searchBST(root.right,value);
    }
    /**
     * 在二叉搜索树中查询是否存在给定值
     * 迭代方式
     */
    public boolean searchBST2(TreeNode root, int value) {
        while(root != null){
            if(value == root.val) return true;
            if(value < root.val) root = root.left;
            else root = root.right;
        }
        return false;
    }

    // 中序遍历方法，方便打印树
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>(); // 记录目标序列
        inorder(root, res); // 递归遍历二叉树
        return res;
    }
    private void inorder(TreeNode root, List<Integer> res) {
        if (root == null) return;
        inorder(root.left, res); // 先遍历左子树节点
        res.add(root.val); // 访问根节点
        inorder(root.right, res); // 再遍历右子树节点
    }
}
